/**
 * 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * 
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 
 * 示例 2：
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * 
 * 提示：
 * 1 <= intervals.length <= 10^4
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 10^4
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */
package zw;

import java.util.ArrayList;

public class T56 {
	public int[][] merge(int[][] intervals) {
		for(int j = intervals.length-1; j > 0 ; j--) {
			for(int i = 0; i + 1 <= j; i++) {
				if(intervals[i][0] > intervals[i+1][0]) {
					int[] temp = intervals[i+1];
					intervals[i+1] = intervals[i];
					intervals[i] = temp;
				}
			}
		}
		
		ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < intervals.length; i++) {
			ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
			tempArrayList.add(intervals[i][0]);
			tempArrayList.add(intervals[i][1]);
			temp.add(tempArrayList);
		}
		
		for(int i = 0; i+1 < temp.size(); i++) {
			if(temp.get(i).get(1) >= temp.get(i+1).get(0)) {
				ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
				tempArrayList.add(temp.get(i).get(0));
				if(temp.get(i).get(1) < temp.get(i+1).get(1)) {
					tempArrayList.add(temp.get(i+1).get(1));
				} else {
					tempArrayList.add(temp.get(i).get(1));
				}
				temp.remove(i);
				temp.remove(i);
				temp.add(i, tempArrayList);
				i--;
			}
		}
		
		int[][] ans = new int[temp.size()][2];
		for(int i = 0; i < temp.size(); i++) {
			ans[i][0] = temp.get(i).get(0);
			ans[i][1] = temp.get(i).get(1);
		}
		return ans;
    }
	
	public static void main(String[] args) {
		T56 t56 = new T56();
		System.out.print(t56.merge(new int[][] {{1,4},{4,5},{8,10},{15,18}}));
	}
}
